package hot100;

import com.链表.练习题.ListNode;

public class g13_合并K个升序链表 {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists == null || lists.length == 0) return null;
        return split(lists, 0, lists.length - 1);
    }
    public ListNode split(ListNode[] lists, int i, int j){
        if(j==i) {
            return lists[i];
        }
        int mid = (j+i) >>> 1;
        return mergeTwoLists(split(lists,i,mid),split(lists,mid+1,j));
    }
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode s=new ListNode(-1,null);
        ListNode p=s;
        while(list1!=null && list2!=null) {
            if(list1.val<list2.val) {
                p.next=list1;
                list1=list1.next;
            }else {
                p.next=list2;
                list2=list2.next;
            }
            p=p.next;
        }
        if(list1!=null) {
            p.next=list1;
        }
        if(list2!=null) {
            p.next=list2;
        }
        return s.next;
    }
}
